package com.jiang.专题.动态规划.Q322;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/05 23:52
 */
class Solution {
    // 动态规划
    // public int coinChange(int[] coins, int amount) {
    //     int[] dp = new int[amount + 1]; // dp[i] 表示凑成金额i所需最少得硬币个数
    //     Arrays.fill(dp, amount + 1);
    //     dp[0] = 0;
    //     for (int i = 1; i <= amount; i++) {
    //         for (int j = 0; j < coins.length; j++) {
    //             if (coins[j] <= i) {
    //                 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
    //             }
    //         }
    //     }
    //     return dp[amount] > amount ? -1 : dp[amount];
    // }
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // dp[i] 表示凑成金额i所需最少得硬币个数
        return dfs(coins, amount, dp);
    }

    public int dfs(int[] coins, int amount, int[] dp) {
        if (amount < 0)  return -1;
        if (amount == 0) return 0;
        if (dp[amount] != 0) return dp[amount];

        int min = Integer.MAX_VALUE;
        for(int coin: coins) {
            int temp = dfs(coins, amount - coin, dp); // 找出凑成金额i - coin所需最少得硬币个数
            if (temp >= 0 && temp < min) min = temp + 1;
        }
        dp[amount] = Integer.MAX_VALUE == min ? -1 : min; // 如果Integer.MAX_VALUE == min，则不能凑出金额i - coi
        return dp[amount];
    }
}
